The shortest-path problem is an important problem in graph theory because it has multiple practical applications in areas such as communications, transportation, and electronics. Well-known variants of the shortest-path problem include the all-pairs shortest-path problem and the single-source shortest-path problem. The present disclosure is primarily concerned with the single-source shortest-path problem, but may be used in conjunction with the all-pairs shortest-path problem if desired.
When solving the single-source shortest-path problem, the objective is to find the shortest path from a single source vertex to all other vertices in the graph. More specifically, we assume a directed multigraph G=<V, E>, where V is a set of n vertices, {v1, v2, . . . , vn}, E is a set of a edges, {e1, e2, . . . , ea}, an edge connects a pair of vertices, and a non-negative length, {l1, l2, . . . , la}, is assigned to each edge. Then, if v1 is selected as the source vertex, the problem is to find the shortest path from v1 to vi for i=2 to n, where a path is a set of edges and the length of a path is the sum of the length of each edge comprising the path.
By way of example, FIG. 1 illustrates a directed graph having a number of vertices {v0, v1, v2, v3, . . . v9}, sometimes referred to herein as nodes. Vertex v0 will be considered the source vertex. The graph shows a number of edges that connect pairs of the vertices and each edge includes a length, sometimes referred to herein as distance. Sometimes the edges are referred to herein as paths and the length of the edges is sometimes referred to as distance. Referring to FIG. 1, by way of example, the edges between source vertex v0 and vertices v1 and v2 both have a length 1, while the edge between vertices v1 and v7 has a length 5, and the edge between vertices v2 and v7 has a length 6. Thus, the shortest path length from source vertex v0 to vertex v7 is through vertex v1 and has a path length of 6. While other paths between source vertex v0 and vertex v7 are possible, e.g., through vertices v4, v5, and v1, as can be seen from FIG. 1, the sum of the edges in the other paths is greater than 6. As is well understood in the art, the length of an edge may represent, e.g., the physical separation between vertices, the cost, or speed of communication over a link between vertices or other similar type of attributes.
Dijkstra's process is a well-known solution to the single-source shortest-path problem that has been widely implemented. One particularly significant application of Dijkstra's process has been in conjunction with link-state routing protocols, such as the Open Shortest Path First (OSPF) routing protocol, defined by the Internet Engineering Task Force (IETF) in RFC 2328, and the Open System Interconnection (OSI) Integrated System-Integrated System (IS-IS) routing protocol defined by the International Standards Organization (ISO). In the routing protocol application, each router runs Dijkstra's process on a graph representing the network topology. Each router uses the vertex representing itself as the source vertex. The result is a set of shortest paths to all other routers in the network. The shortest paths are then used to build the routing database that is utilized to forward packets to the appropriate destination.
For large graphs, Dijkstra's process can be computationally intensive. Naturally, the time required to solve the shortest-path problem is important in many applications. As an example, in the routing protocol application, the shortest paths need to be recomputed when the network topology changes, such as when there is failure of communication links or communication equipment. In this case, the time required to solve the shortest-path problem can be a significant component of the time required to restore network stability. Furthermore, efficient solution of the shortest-path problem is becoming increasing important with the advent of constraint-based routing, which can require multiple iterations of the shortest-path process to build a routing database that conforms to the desired constraints.
Thus, what is needed is a shortest path search system and method that increases efficiency relative to the conventional Dijkstra's process, thereby reducing the amount of time to calculate a solution.